package com.tgy.algorithm.base._递归;

public class _N皇后问题01 {

    public static int queen(int n) {

        int[] locs = new int[n];
        return doQueen(0,locs);
    }

    public static int doQueen(int index,int[] locs) {

        int len = locs.length;
        if (index == locs.length) {
            // 有一个方案
            return 1;
        }

        int result = 0;
        for (int i = 0; i < len; i++) {
            // [index,i]
            locs[index] = i;
            // [i,locs[i]
            if (isValid(locs,index)) {
                result += doQueen(index+1,locs);
            }
        }

        return result;
    }

    public static boolean isValid(int[] locs,int index) {

        // [index,locs[index]]
        for (int i = 0; i < index; i++) {
            // [i,loc[i]]
            if (locs[index] == locs[i] || Math.abs(index - i) == Math.abs(locs[index] - locs[i])) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {

        int queen = queen(4);
        System.out.println(queen);
    }
}
